package 优先算法.递归_搜索与回溯.穷举vs暴搜vs深搜vs回溯vs剪枝.子集;


import java.util.ArrayList;
import java.util.List;

/**
 *https://leetcode.cn/problems/subsets/
 */
public class Main {
    public static void main(String[] args) {
        Solution so = new Solution();

    }
}
class Solution {
    static List<List<Integer>> ret;
    static List<Integer> path;

    public List<List<Integer>> subsets(int[] nums) {
        ret = new ArrayList<>();
        path = new ArrayList<>();
        dfs(nums,0);
        return ret;
    }
    public static void dfs(int[] nums , int pos){
        ret.add(new ArrayList<>(path));
        for(int i= pos ; i < nums.length;i++){
            path.add(nums[i]);
            dfs(nums,i + 1);
            path.remove(path.size() -1);
        }

    }

    /*public List<List<Integer>> subsets(int[] nums) {
        ret = new ArrayList<>();
        path = new ArrayList<>();
        dfs(nums,0);
        return ret;
    }
    public static void dfs(int[] nums , int i){
        if( i == nums.length){
            ret.add(new ArrayList<>(path));
            return;
        }
        //选
        path.add(nums[i]);
        dfs(nums,i+1);
        path.remove(path.size()-1);
        //不选
        dfs(nums,i+1);

    }*/
}